from typing import List, Tuple
import time

def insertion_sort(A: List[int]) -> Tuple[List[int], float]:
    """
    严格符合形式化定义的插入排序实现
    参数:
        A: 输入整数数组 (a₁, a₂, ..., aₙ)
    返回:
        (B, T): 排序后数组和耗时(秒)
    """
    B = A.copy()
    start = time.perf_counter()
    
    for i in range(1, len(B)):
        key = B[i]
        j = i-1
        while j >=0 and B[j] > key:
            B[j+1] = B[j]
            j -= 1
        B[j+1] = key
    
    elapsed = time.perf_counter() - start
    return (B, elapsed)

def verify_sorting(A: List[int], B: List[int]) -> bool:
    """验证排序结果满足形式化要求"""
    # 元素完整性检查
    if sorted(A) != sorted(B):
        return False
    
    # 顺序约束检查
    for i in range(len(B)-1):
        if B[i] > B[i+1]:
            return False
    
    return True